Byzantine quorum
Why Byzantine quorum is$ 2f + 1?
$ nnodes, $ fByzantine nodes, $ n - fhonest nodes
Let$ abe the quorum
For safety:
Assume that honest nodes are devided into two sets equally and Byzantine nodes vote for the both
In this case, the number of votes must be lower than the quorum for safety
$ (n - f)/2 + f < a
$ ∴ (n + f)/2 < a(1)
For liveness, honest nodes must be able to form a quorum
$ n - f ≧ a(2)
From (1) and (2), for the existence of$ a,
$ (n + f) / 2 < n - f
$ f < n/3
$ ∴ n \geq 3f +1
If $ n = 3f + 1, from (1) and (2),
$ (4f + 1)/2 < a \leq 2f + 1
$ ∴ a = 2f + 1
minaminao.icon < If $ n=kf,
$ (k+1)f/2 < a \le (k-1)f
$ \frac{(k+1)n}{2k} < a \le \frac{(k-1)n}{k}
$ k=1: $ n<a \le 0 (impossible)
$ k=2: $ \frac{3n}{4}<a \le \frac{n}{2} (impossible)
$ k=3: $ \frac{2n}{3}< a \le \frac{2n}{3} (impossible)
$ k=4: $ \frac{5n}{8} < a \le \frac{3n}{4}
$ k\to \infty: $ \frac{n}{2}<a\le n
Message complexity of quorum voting
Authenticator complexity: $ O(n^2) All nodes receive 2f + 1 of votes and every vote is$ O(1)
PBFT's view-change: $ O(n^3)Each message includeds 2f + 1 of votes for a latest checkpoint i.e.$ O(n)
nrryuya.icon > Each votes for a checkpoint can be aggregated. Any set of votes for a checkpoint is allowed -> view-change messages can not be aggregated ->$ O(n^2)at least
Message complexity: All to All ->$ O(n^2), Leaderful Hub and Spoke ->$ O(n)
nrryuya.icon > Gossip?
Synchronous
The threshold is $ f + 1
In synchronous assumption, validators vote for the same block (i.e. no split) if the leader is honest